/**
 * 二次优化的冒泡排序，在记录当前轮次是否发生过排序的基础上，再记录上次发生交换的位置
 * 下一轮比较时，比较上一轮中最后发生交换的位置，后面的位置没有发生过交换，说明已经有序了
 * 如果有一轮比较中从头到尾否没有发生过排序，就说明排序已经完成了
*/

// 交换元素
function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

const bubbleSort = (arr) => {
  let swapped = true,
    // 最后一个没有经过排序的元素的下标
    indexOfLastUnsortedElement = arr.length - 1,
    // 上次发生交换的位置
    swappedIndex = -1
  while (swapped) {
    swapped = false
    for (let i = 0; i < indexOfLastUnsortedElement; i++) {
      if (arr[i] > arr[i + 1]) {
        // 如果左边的数大于右边的数，则交换，保证右边的数字最大
        swap(arr, i, i + 1)
        // 表示发生了交换
        swapped = true
        // 更新交换的位置
        swappedIndex = i
      }
    }
    // 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
    indexOfLastUnsortedElement = swappedIndex
  }
  return arr
}

console.log(bubbleSort([4, 3, 0, 1, 2]))